Authenticated Encryption (AE) is a technique for encrypting a plaintext message and giving a message authentication code (MAC) thereto at the same time by use of a previously-shared secret key. The use of authenticated encryption enables contents to be protected against eavesdropping, and unauthorized manipulation to be detected. If authenticated encryption is applied to communication paths, strong protection for the contents to be communicated can be achieved.
Basic input and output of authenticated encryption will be described below. Two persons sharing a secret key K will be assumed below as Alice and Bob, and a message encrypted by authenticated encryption is assumed to be communicated from Alice to Bob.
An encryption function and a decode function for authenticated encryption are assumed as AEnc_K and ADec_K, respectively. A plaintext to be encrypted is assumed as M and a variable N called initial vector is introduced. The initial vector N is generally a random number with a short fixed length or a counter, which is generated by Alice.
The encryption processing on Alice side will be first described. Alice generates the initial vector N, and then executes (C, T)=AEnc_K(N, M). Herein, AEnc_K is called encryption function using the key K as a parameter, C is called encrypted text, and T is called authenticated tag, which are variables for detecting an altered fixed length. Alice transmits a combination (N, C, T) of initial vector N, resultant encrypted text C, and resultant authentication tag T to Bob.
The decode processing on Bob side will be described below. Herein, the information which Bob receives from Alice is assumed as (N′, C′, T′). When receiving the information from Alice, Bob executes ADec_K(N′, C′, T′) as the decode processing. ADec_K is a decode function using the key K as a parameter. If communication is altered in the middle and (N′, C′, T′) is different from (N, C, T), assuming a symbol indicating alternation as ¥bot, ADec_K(N′, C′, T′) outputs ¥bot. Without alternation and in the case of (N′, C′, T′)=(N, C, T), ADec_K(N′, C′, T′) outputs a decoded plaintext M′ having the same contents as the plaintext M encrypted by Alice. Thereby, M is correctly decoded.
Practically, the input and output include a variable called header H in many cases. The header H is not to be encrypted, but is information for message authentication to be used for expressing a protocol version or the like, for example.
With the header H included, the encryption function is input/output of (C, T)=AEnc_K(N, M, H), and encrypts the plaintext M and gives a message authentication code to a combination of plaintext M and header H. Alice transmits a combination (N, H, C, T) of initial vector N, header H, resultant encrypted text C, and resultant authentication tag T to Bob.
When input/output of ADec_K(N′, C′, T′, H′) is obtained and (N′, C′, T′, H′) is different from (N, C, T, H), the decode function outputs the symbol bot indicating alternation. When the received (N′, H′, C′, T′) is not altered or (N′, H′, C′, T′)=(N, H, C, T) is established, Bob on the reception side can correctly decode M and confirm that the header H is not altered.
The authenticated encryption with the input/output added with the header H may be called authenticated encryption with associated data (AEAD), and will be simply denoted as “authenticated encryption” below unless otherwise stated.
One of the authenticated encryption realization methods is based on generic composition. This is a method using a combination of secure encryption system and secure MAC system. For example, with a well-known combination Enc-then-Auth, two keys K1 and K2 are used to realize authenticated encryption with (C, T)=MAC_K2(N, Enc_K1(M)). Herein, Enc_XX indicates an encryption function used in the encryption system, and MAC_XX indicates a MAC given function used in the MAC system.
When block encryption such as AES (Advanced Encryption Standard) encryption is used, for example, the encryption system may employ AES counter mode encryption, and the MAC system may employ CMAC-AES (Cipher-based MAC-AES). Further, as a method for performing authenticated encryption by use of one block encryption key without the use of two keys, there is known an authenticated encryption system called CCM mode (Counter with CBC-MAC) (Non-Patent Literature 1, for example).
However, all the above methods require two-pass processings including encryption and MAC giving. That is, data needs to be entirely scanned at least twice. Further, when an input plaintext is of m blocks, the block encryption needs to be called about m times for encryption and MAC function used in the CCM system. Therefore, the block encryption needs to be called about 2 m times for the authenticated encryption processing on an m-block plaintext. That is, the processing function such as encryption function or MAC given function needs to be called twice per plaintext block. The system in which the processing function is called twice for each block is also called two-rate system. The two-pass or two-rate system has a problem that the processing takes a long time and has a heavy load.
One approach for solving the problem is a one-pass authenticated encryption system using block encryption.
An authenticated encryption system called OCB mode described in Patent Literature 1 is first proposed (which will be called OCB system below). The OCB system is such that block encryption called Tweakable block encryption described in Non-Patent Literature 2 is extended.
The Tweakable block encryption is an authenticated encryption system in which an auxiliary variable called Tweak is introduced to encryption and decode. When a block size is n-bit, encryption with the Tweakable block encryption can be expressed as “TE_K(Tw, M)=C,” and decode can be expressed as “TD_K(Tw, C)=M.” For any combination (K, Tw), TE_K(Tw, *) configures substitution in the n-bit space. Its inverse substitution is TD_K(Tw, *). Tw indicates an auxiliary variable Tweak, and * indicates a variable. The auxiliary variable Tw is required for decode, but if it is released, the safety of the Tweakable block encryption is not influenced.
In the OCB system, at first, an encryption function of typical block encryption is converted into an encryption function of Tweakable block encryption or a Tweak-assigned encryption function by use of an XEX mode described in Non-Patent Literature 3. Then, the following TE_K function is called to encrypt an initial vector N and a plaintext M=(M[1], M[2], . . . , M[m]). Each M[i] is assumed as n-bit block. The TE_K function used in the OCB system employs a variable (N, i) corresponding to Tweak. N indicates an initial vector and i indicates a block identification number.
            C      ⁡              [        1        ]              =          TE_K      ⁢              (                              (                          N              ,              1                        )                    ,                      M            ⁡                          [              1              ]                                      )              ,          ⁢            C      ⁡              [        2        ]              =          TE_K      ⁢              (                              (                          N              ,              2                        )                    ,                      M            ⁡                          [              2              ]                                      )              ,          ⁢  …  ⁢          ,          ⁢            C      ⁡              [        m        ]              =          TE_K      ⁢              (                              (                          N              ,              m                        )                    ,                      M            ⁡                          [              m              ]                                      )            
An authentication tag T is found by calling the same TE_K function as the message as follows, for example, for SUM=M[1] xor M[2] xor . . . M[m] which is XOR (exclusive OR) of all the plaintext blocks.T=TE_K((N,m+1),SUM)
The TE_K function used in the OCB system is executed by adding Tw=(N, i) and a sequence mask_K(N, i) calculated by the secret key K to the input/output of the encryption function E_K of block encryption (converted in the XEX mode). The conversion equation in the XEX mode is expressed as follows. The conversion equation may be called XEX conversion equation below.TE_K((N,i),M[i])=E_K(M[i]xor mask_K(N,i)xor mask_K(N,i)
E_K is used for calculating mask, and efficient sequential processings are enabled in the OCB system. That is, calculations from mask_K(N, i) to mask_K(N, i+1) can be efficiently made.
FIG. 19 is an explanatory diagram schematically illustrating an encryption processing in the OCB system. In FIG. 19, the blocks in dashed lines correspond to TE_K((N, i), *). The progress of a processing of calculating a mask sequence is omitted in FIG. 19.
As illustrated in FIG. 19, E_K is called once for calculating L for finding a mask sequence and an authentication tag T, respectively, in the OCB system, but a one-pass processing is possible as a whole. Further, the processing in each block can be performed in parallel except the calculation of a mask sequence. More specifically, the number of calls of block encryption for an m-block plaintext is almost m, and is almost half that of other two-pass authenticated encryption systems such as CCM system and GCM (Galois/Counter mode) system.